/// @tags:
#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

namespace BlueQuantum {

constexpr int MAXN = 3e5 + 3, ST = 19;

int n, m, T;
int st[MAXN][ST], w[MAXN], fl[MAXN], fr[MAXN], sl[MAXN], sr[MAXN], lg[MAXN];
int s[MAXN], top;

inline int cmp(int x, int y) { return w[x] > w[y] ? x : y; }

inline int main() {
  cin >> n >> m >> T;
  for (int i = 1; i <= n; ++i) cin >> w[i], st[i][0] = i;
  for (int i = 2; i <= n; ++i) lg[i] = lg[i / 2] + 1;
  for (int j = 1; j <= lg[n]; ++j) {
    for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
      st[i][j] = cmp(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
    }
  }
  for (int i = 1; i <= n; ++i) {
    while (top >= 1 && w[s[top]] < w[i]) top--;
    fl[i] = s[top];
    s[++top] = i;
  }
  top = 0;
  for (int i = n; i >= 1; --i) {
    while (top >= 1 && w[s[top]] < w[i]) top--;
    fr[i] = s[top];
    s[++top] = i;
  }
  for (int i = 1; i <= n; ++i) {
    if (fl[i]) {
      sl[fl[i]]++;
      sr[i]++;
    }
    if (fr[i]) {
      if (w[i] == w[fr[i]]) continue;
      sl[i]++;
      sr[fr[i]]++;
    }
  }
  for (int i = 1; i <= n; ++i) {
    sl[i] += sl[i - 1];
    sr[i] += sr[i - 1];
  }
  for (int l, r, ans = 0; m; --m) {
    cin >> l >> r;
    if (T) {
      int p = (l + ans - 1) % n + 1, q = (r + ans - 1) % n + 1;
      l = min(p, q), r = max(p, q);
    }
    int k = lg[r - l + 1];
    int maxpos = cmp(st[l][k], st[r - (1 << k) + 1][k]);
    ans = sl[maxpos - 1] - sl[l - 1] + sr[r] - sr[maxpos];
    cout << ans << '\n';
  }
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("friend.in", "r", stdin);
  freopen("friend.out", "w", stdout);
#endif
#endif

  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
